package com.clstu.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * dij..算法解决最短路径问题
 */
public class Dij {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        //思路分析:
        //Dijst..算法,每一次都找到最短距离的点,把它确定下来,再再它的基础上计算新的没有
        //算过距离的节点,下一次再这样....直到所有点都标记
        //集合记录每个起点能到达的城市的最短距离
        HashMap<Node,HashMap<Node,Integer>> set = new HashMap<>();
        //创建图
        Graph graph =createGraph(n,edges);
        //遍历图,每个节点依次作为起点,保存每个节点能够到达的信息
        for(int i=0;i<graph.nodes.size();i++){
            //起点
            Node start = graph.nodes.get(i);
            HashMap<Node,Integer> dises = new HashMap<>();
            //dij..算法
            //头节点入
            HashSet<Node> sure = new HashSet<>();//用于标记已经确定号的点
            dises.put(start,0);
            while(true){
                //如果找完
                if(sure.size() == n){
                    break;
                }

                //从距离集合中找到一个距离出发点最小的点固定(未固定的)
                int minDis = 100000;
                Node minNode = null;
                for (Map.Entry<Node, Integer> entry : dises.entrySet()) {
                    Node key = entry.getKey();
                    Integer curD = entry.getValue();
                    //如果是最小
                    if(minDis>curD && !sure.contains(key)){
                        minDis = curD;
                        minNode = key;
                    }
                }

                //把最小的点固定,之后再加入它的连接的距离节点
                if(minNode!=null) sure.add(minNode);
                assert minNode != null;
                for (Edge edge : minNode.edges) {
                    if(!dises.containsKey(edge.to)){
                        dises.put(edge.to,minDis+edge.weight);
                    }else {
                        dises.put(edge.to,Math.min(dises.get(edge.to),minDis+edge.weight));
                    }
                }

            }
            //加入到距离map里面
            set.put(start,dises);
        }
        //找到最多少城市的点
        Node res = null;
        int minCites = n;
        for (Map.Entry<Node, HashMap<Node, Integer>> entry : set.entrySet()) {
            Node key = entry.getKey();
            int cities = entry.getValue().size();
            if(cities<minCites){
                minCites = cities;
                res = key;
            }
        }
        return res.id;
    }

    //编写方法,将传入的二维数组创建成图返回
    public Graph createGraph(int n,int[][] edges){
        //创建节点
        ArrayList<Node> nodes = new ArrayList<>();
        for(int i = 0;i< n;i++){
            nodes.add(new Node(i));
        }
        //连接边
        ArrayList<Edge> edgs = new ArrayList<>();
        for(int i=0;i<edges.length;i++){
            //取出信息
            Node from = nodes.get(edges[i][0]);
            Node to = nodes.get(edges[i][1]);
            int weight = edges[i][2];
            //创建边
            Edge edge = new Edge(from,to,weight);
            edgs.add(edge);
            //修改关系
            from.out++;
            to.in++;
            from.edges.add(edge);
            from.nexts.add(to);
        }
        return new Graph(nodes,edgs);
    }
}
/**
 定义图类,包含点集和边集
 */
class Graph{
    ArrayList<Node> nodes = null;//点集
    ArrayList<Edge> edges = null;//边集
    //构造器
    public Graph(ArrayList<Node> nodes,ArrayList<Edge> edges){
        this.nodes = nodes;
        this.edges = edges;
    }
    //编写方法,删除节点和它的影响
    public void delete(Node node){
        nodes.remove(node);
        Node cur = null;
        for(int i=0;i<node.nexts.size();i++){
            node.nexts.get(i).in--;
        }
    }
}
/***
 节点类,包含值和边集和下一跳
 */
class Node{
    public int id;//城市编号
    public int in;//入读
    public int out;//出度
    ArrayList<Node> nexts = null;//吓一跳
    ArrayList<Edge> edges = null;//边集
    //构造器
    public Node(int id){
        this.id = id;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", in=" + in +
                ", out=" + out +
                '}';
    }
}
/**
 边类,包含from to weight
 */
class Edge{
    public Node from;//重点
    public Node to;//起点
    public int weight;
//    public String[] ss = new String[100];
    //构造器
    public Edge(Node f, Node t,int w){
        from = f;
        to = t;
        weight = w;
    }
}
